package Hot100;

import LinkedList.ListNode;

public class 反转链表 {
    public ListNode reverseList(ListNode head) {
        // 迭代
        /*if (head == null || head.next == null) return head;
        ListNode prev;
        ListNode curr = head;
        ListNode aftr = head.next;
        curr.next = null;
        while (aftr != null) {
            prev = curr;
            curr = aftr;
            aftr = aftr.next;
            curr.next = prev;
        }
        return curr;*/

        // 从前向后递归
        //return reverse(null, head);

        // 从后向前递归（难度较大）
        // 边缘条件判断
        if (head == null || head.next == null) return head;
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) return prev;
        ListNode temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        return reverse(cur, temp);// 更新prev、cur位置
    }
}
